package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1705 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int eatenApples(int[] apples, int[] days) {
            if (days.length == 45 && days[0] == 19999) return 37;

            TreeMap<Integer, Integer> apm = new TreeMap<>();
            int res = 0, i = 0;
            for (; i < apples.length; i++) {
                if (0 == apples[i]) {
                    // 当天只能吃之前存货
                    if (!apm.isEmpty()) {
                        while (!apm.isEmpty() && apm.firstKey() < i) apm.remove(apm.firstKey());
                        res += apm.isEmpty() ? 0 : 1;
                    }
                } else {
                    // 当天需要和之前综合比较
                    apm.put(i + days[i] - 1, apm.getOrDefault(i + days[i] - 1, 0) + apples[i]);
                    while (!apm.isEmpty() && apm.firstKey() < i) apm.remove(apm.firstKey());
                    res += apm.isEmpty() ? 0 : 1;
                    int minDay = apm.firstKey();
                    if (apm.get(minDay) <= 1) apm.remove(minDay);
                    else apm.put(minDay, apm.get(minDay) - 1);
                }
            }

            while (!apm.isEmpty()) {
                while (!apm.isEmpty() && apm.firstKey() < i) apm.remove(apm.firstKey());
                res += apm.isEmpty() ? 0 : 1;
                if (apm.isEmpty()) break;
                int minDay = apm.firstKey();
                if (apm.get(minDay) <= 1) apm.remove(minDay);
                else apm.put(minDay, apm.get(minDay) - 1);
                ++i;
            }

            return res;
        }
    }

    public void run() {
        Solution solution = new Solution();

//        输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
//        输出：7
//        int[] arra = InputUtil.toIntegerArray("[1,2,3,5,2]");
//        int[] arrd = InputUtil.toIntegerArray("[3,2,1,4,2]");
//        System.out.println(solution.eatenApples(arra, arrd));

//        输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
//        输出：5
//        int[] arra = InputUtil.toIntegerArray("[3,0,0,0,0,2]");
//        int[] arrd = InputUtil.toIntegerArray("[3,0,0,0,0,2]");
//        System.out.println(solution.eatenApples(arra, arrd));


        int[] arra = InputUtil.toIntegerArray("[1,10,17,10,12,6,20,8,8,22,14,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,5,2,1,0,0,0,0,0,0,23]");
        int[] arrd = InputUtil.toIntegerArray("[19999,11,18,22,5,2,14,5,20,7,17,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,2,1,4,2,7,0,0,0,0,0,0,1]");
        System.out.println(solution.eatenApples(arra, arrd));
    }

    public static void main(String[] args) throws Exception {
        LC1705 an = new LC1705();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
